<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script src="dict.js"></script>
<script>
    //封装队列
    function Queue(){
        //属性
        this.items = []

        Queue.prototype.enqueue = function (element){
            this.items.push(element)
        }

        Queue.prototype.dequeue = function (){
            return this.items.shift()
        }

        Queue.prototype.front = function (){
            return this.items[0]
        }

        Queue.prototype.isEmpty = function (){
            return this.items.length == 0;
        }

        Queue.prototype.size = function (){
            return this.items.length
        }
    }
    //封装图结构
    function Graph(){
        //属性:顶点(数组)/边(字典)
        this.vertexes =[] //顶点
        this.edges = new Dictionay() //边

        //方法
        //添加顶点方法
        Graph.prototype.addVertex = function (v){
            this.vertexes.push(v);
            this.edges.set(v,[])
        }

        //添加边的方法
        Graph.prototype.addEdges = function (v1,v2){
              this.edges.get(v1).push(v2);
              this.edges.get(v2).push(v1);
        }

        //实现toString
        Graph.prototype.toString = function (){
            //1.定义字符串,保有最终的结果
            var resultString = ""

            //2.遍历所有的顶点，以及所有的边
            for(var i=0; i<this.vertexes.length;i++){
                resultString+=this.vertexes[i] + "->" +" "
                var Edges = this.edges.get(this.vertexes[this.vertexes[i]])
                for (var j=0; j<Edges.length; j++){
                    resultString+= Edges[i] + "";
                }
              resultString += '\n';
            }
            return resultString;            ``
        }

        //初始化颜色
        Graph.prototype.initializeColor = function (){
            var colors = []
            for (var i=0; i<this.vertexes.length;i++){
                  colors[this.vertexes[i]] = 'white'
            }
            return colors
        }

        //广度优先搜索(BFS)
        Graph.prototype.bfs = function (initV,handler){
             //定义颜色
            var colors = this.initializeColor();

            //定义队列
            var queue = new Queue();

            queue.enqueue(initV);

            while (!queue.isEmpty()){

                 var v =  queue.dequeue();

                 var vList = this.edges.get(v);

                 colors[v] = 'gray'

                 for (var  i=0; i<vList.length;i++){
                        if(colors[vList[i]] == 'white'){
                            colors[vList[i]] = 'gray';
                            queue.enqueue(vList[i])
                        }
                 }
                handle(v)

                colors[v] = 'black'
            }

        }

        //深度优先搜索(DFS)
        Graph.prototype.bfs = function (initV,handler){
            //定义颜色
            var colors = this.initializeColor();

            this.dfsVisit(initV,colors,handler)

        }
        Graph.prototype.dfsVisit = function (v,colors,handle){

                 colors[v] = 'gray';

                 handle(v)

                 var vList = this.edges.get(v);

                 for (var i = 0; i<vList.length; i++){
                      var e = vList[i];
                      if(colors[e] == 'white'){
                          this.dfsVisit(e,colors,handle)
                      }
                 }

                 colors[v] = 'black';
        }

     }
     </script>
</body>
</html>